package com.LC._17;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public HashMap<Character, String> phoneMap;// 申明全局便于访问
    public List<String> list;
    // 深度优先，进行回溯
    public List<String> letterCombinations(String digits) {
        list = new ArrayList<>();
        if (digits == null || digits.length() == 0) {//判断空
            return list;
        }
        phoneMap = new HashMap<Character, String>() ;// 利用哈希表构建电话表
        phoneMap.put('2', "abc");
        phoneMap.put('3', "def");
        phoneMap.put('4', "ghi");
        phoneMap.put('5', "jkl");
        phoneMap.put('6', "mno");
        phoneMap.put('7', "pqrs");
        phoneMap.put('8', "tuv");
        phoneMap.put('9', "wxyz");
        dfs(new StringBuilder(), digits, 0);
        return list;
    }
    public void dfs(StringBuilder builder, String digits, int index) {
        //将拼接好的字符串存到list中 数组最后一个下标length-1 index==level
        if (index == digits.length()) {// 如果此时长度大于digits的长度，就写入list中
            list.add(builder.toString());//将拼接好的字符串添加到list中
            return;
        }
        String str = phoneMap.get(digits.charAt(index)); //获取value值
        //回溯法的递归要在for循环中
        for (int i = 0; i < str.length(); i++) {
            builder.append(str.charAt(i));// 利用stringbuilder 便于添加字符，把单个字母添加到stringbuilder中
            dfs(builder, digits, index + 1); // 深度优先遍历下一个数字对应的字符串
            builder.deleteCharAt(builder.length() - 1); //从最后一层开始 删除掉前一个字符 返回上一级
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        String digits= "23";
        System.out.println(solution.letterCombinations("23"));
    }
}